/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-12
 * Time: 23:40
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode node1;
    public TreeNode node2;
    public void recoverTree(TreeNode root) {
        TreeNode cur=root;
        TreeNode pre=null;//记录前一个节点
        while(cur!=null){
            //判断有没有左子树
            if(cur.left!=null){
                //有左子树
                TreeNode rightest=cur.left;//记录最右边的节点
                //找到左子树中序遍历的最后一个节点
                while(rightest.right!=null&&rightest.right!=cur){
                    rightest=rightest.right;
                }
                if(rightest.right==null){
                    //说明左子树还没有遍历
                    rightest.right=cur;
                    cur=cur.left;
                }else{
                    //左子树已经被遍历过了
                    if(cur.val<pre.val){
                        //说明节点错误
                        if(node1==null){
                            node1=pre;//第一个是找大的
                        }
                        node2=cur;//第二个是找小的,注意每次找到错误节点是,node2也要赋值,防止只有一个位置出错,只找出一个节点
                    }
                    rightest.right=null;//先置空
                    pre=cur;
                    cur=cur.right;
                }
            }else{
                //没有左子树
                if(pre!=null&&cur.val<pre.val){
                    //说明节点错误
                    if(node1==null){
                        node1=pre;//第一个是找大的
                    }
                    node2=cur;//第二个是找小的,注意每次找到错误节点是,node2也要赋值,防止只有一个位置出错,只找出一个节点
                }
                pre=cur;
                //遍历右子树
                cur=cur.right;
            }
        }
        //开始交换节点的内容
        int temp=node1.val;
        node1.val=node2.val;
        node2.val=temp;
    }
}
